#ifndef __BINARTREE__H_
#define __BINARTREE__H_
#include <iostream>
#include <DoubleLinkvoid.h>
#include <LinkQueue.h>

class BinaryTree
{
public:
    using ElementType = int;
    BinaryTree();
    // 插入
    void Insert(const ElementType &element);

    // 按值删除
    void Remove(const ElementType &element);

    // 按值查找
    ElementType *FindByElement(const ElementType &element);

    void show();

private:
    struct Node
    {
        Node(const ElementType &data) : data(data)
        {
            left = right = nullptr;
        }
        ElementType data;
        Node *left;
        Node *right;
    };

    Node *InsertNode(Node *node, const ElementType &element);

    Node *RemoveNode(Node *node, const ElementType &element);

    void PreTravel(Node *node);
    void MidTravel(Node *node);
    void BackTravel(Node *node);
    void HeightTravel(Node *node);

    Node *GetMinNode(Node *node);
    ElementType *FindElement(Node *node, const ElementType &element);

    // 右旋
    Node *RotateRight(Node *node);
    // 左旋
    Node *RotateLeft(Node *node);
    // 左右旋
    Node *RotateLeftRight(Node *node);
    // 右左旋
    Node *RotateRightLeft(Node *node);

    int GetNodeHight(Node *node);
    int LRDevition(Node *node);
    Node *root;
};

#endif